#pragma once

#include <vector>

namespace solution_053
{

class Solution
{
public:
    int maxSubArray(const std::vector<int>& nums)
    {
        int i = 0;
        int max_sum = nums.front();
        for (; i < (int)nums.size() && nums.at(i) <= 0; ++i)
            max_sum = std::max(max_sum, nums.at(i));
        if (i == (int)nums.size())
            return max_sum;

        int sum = 0;
        for (; i < (int)nums.size(); ++i) {
            if (nums.at(i) > 0 && sum <= 0)
                sum = 0;
            sum += nums.at(i);
            max_sum = std::max(max_sum, sum);
        }
        return max_sum;
    }
};

}  /* namespace solution_053 */
